package one.three.four;

import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdIn;

public class Parentheses {

	static class Stack<Item> {

		private Node<Item> first;
		private int n;

		public Stack() {
			first = null;
			n = 0;
		}

		public boolean isEmpty() {
			return first == null;
		}

		public int size() {
			return n;
		}

		public void push(Item item) {
			Node oldfirst = first;
			first = new Node();
			first.item = item;
			first.next = oldfirst;
			n++;
		}

		public Item pop() {
			if (isEmpty()) {
				throw new NoSuchElementException("Stack underflow");
			}
			Item item = (Item) first.item;
			first = first.next;
			n--;
			return item;
		}

		private class Node<Item> {
			Item item;
			Node<Item> next;
		}

		private class LinkedIterator<Item> implements Iterator<Item> {
			private Node<Item> current;

			public LinkedIterator(Node<Item> first) {
				this.current = first;
			}

			@Override
			public boolean hasNext() {

				return current != null;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}

			@Override
			public Item next() {
				if (!hasNext()) {
					throw new NoSuchElementException();
				}
				Item item = current.item;
				current = current.next;
				return item;
			}

		}

	}

	private static boolean parentheses(String s) {
		Stack<String> stack = new Stack<String>();
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			char r;
			if (c == '(' || c == '[' || c == '{') {
				stack.push(c + "");
			}
			if (c == ')') {
				r = stack.pop().charAt(0);
				if (r != '(')
					return false;
			}
			if (c == ']') {
				r = stack.pop().charAt(0);
				if (r != '[')
					return false;
			}
			if (c == '}') {
				r = stack.pop().charAt(0);
				if (r != '{')
					return false;
			}
		}
		if (stack.size() == 0) {
			return true;
		}
		return false;
	}

	public static void main(String[] args) {
		String s = StdIn.readLine();
		boolean r = parentheses(s);

		System.out.println(r);
	}

}
